package leetcode_day._2021._202105._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/12 22:41
 * 子数组异或查询
 * 算法：位运算  前缀和
 * 求出前 n 个元素的位运算，prefix[n + 1]
 * 第 0 个元素为 0
 * [i, j] 之间的异或 = prefix[j + 1] ^ prefix[i]
 */
public class _12_1310 {

    public int[] xorQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        int[] prefix = new int[n + 1];
        prefix[0] = 0;
        for (int i = 1; i < n + 1; i++) prefix[i] = prefix[i - 1] ^ arr[i - 1];
        n = queries.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) ans[i] = prefix[queries[i][1] + 1] ^ prefix[queries[i][0]];
        return ans;
    }
}
